package com.cacheserverdeploy.algorithm;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.cacheserverdeploy.node.ConsumeNode;
import com.cacheserverdeploy.node.NetworkNode;


public class SecondStep {

	/**
	 * 返回服务器
	 * 
	 * @param matrix
	 * @param networkNodes
	 * @param consumeNodes
	 */

	public List<Integer> findSeverLocaltion(int[][] matrix, NetworkNode[] networkNodes, ConsumeNode[] consumeNodes) {		
		int consumeNum = consumeNodes.length;// 消费点个数
		int[] directConnectedNodeIDs = new int[consumeNum];
		// 将于消费点直接相连的点的id存储下来
		for (int i = 0; i < consumeNum; i++) {
			directConnectedNodeIDs[i] = consumeNodes[i].getNetworkNodeId();
		}

		// 存储消费点之间最短距离
		List<List<Integer>> paths = new ArrayList<>();
		// 存储到服务器的最短juli
//		List<List<Integer>> pathsCopy = new ArrayList<>();
		// 存储所有服务器点的路径
//		HashMap<Integer, List<List<Integer>>> severPaths = new HashMap<>();
		// 存储一个服务器路径
		List<List<Integer>> severPath = new ArrayList<>();
		List<List<Integer>> severPath1 = new ArrayList<>();
		SingleSourceDijkstra ssDijkstra = new SingleSourceDijkstra();
		for (int i = 0; i < consumeNum; i++) {
			int start = consumeNodes[i].getNetworkNodeId();
			// 该点到其他所有点的最短距离
			List<List<Integer>> shortPaths = ssDijkstra.dijkstra_Path(matrix, start, directConnectedNodeIDs);
			// 该点到其他消费点最短路径，例如[43,44]
			List<Integer> shortestPath = findMinPath(shortPaths);
//			System.out.println(shortestPath.toString());
			// 全部存储下来
			paths.add(shortestPath);
		}

//		pathsCopy.addAll(paths);// 备份一个

		List<Integer> severID = new ArrayList<>();
		for (int i = 0; i < networkNodes.length; i++) {
			if(networkNodes[i].isLocatedServer()){
				severID.add(networkNodes[i].getId());
			}
		}

		// 当pathsCopy里面的点重复率为2时停止
		while ( paths.size()!=0&&twoLeft(paths) == false ) {
			int id = findMaxNode(paths);// 去除了最后一点,找到出现次数最多的消费节点		
			
			// 流量记录函数
			for (int i = 0; i < paths.size(); i++) {
				if (paths.get(i).contains(id)) {
					severPath.add(paths.get(i));
					severPath1.add(paths.get(i));
					paths.remove(i);
					i--;
				}
			}
			
			int id1=findMaxSever(severPath1);
			
			severID.add(id1);
			networkNodes[id].setLocatedServer(true);//设置为服务器点
			
//			severPaths.put(id, severPath);// 服务器id，以及其位置
			severPath1.clear();
			
		}
		
		
		

		/************************************** 流量判断是否增加服务器 ************************************/
/*
		// 孤立点到最近的服务器
		int[] severGroup = new int[severID.size()];
		for (int i = 0; i < severID.size(); i++) {
			severGroup[i] = severID.get(i);
		}
		
		
		for (int i = 0; i < consumeNodes.length; i++) {
			int start = consumeNodes[i].getNetworkNodeId();
			if (!networkNodes[start].isLocatedServer()) {
				// 有可能是服务器本身
				// 该点到其他所有点的最短距离

				// 这儿一定要注意，调用了最短函数之后，会修改本身的邻接矩阵
				int[][] matrix2 = Util.constructMatrix(networkNodes);
				List<List<Integer>> shortPaths = ssDijkstra.dijkstra_Path(matrix2, start, severGroup);
				// 该点到其他消费点最短路径，例如[43,44]
				List<Integer> shortestPath = ssDijkstra.findMinPath(shortPaths);
				// System.out.println(shortestPath.toString());
				// 全部存储下来
				pathsCopy.add(shortestPath);
			}

		}
		
		// 现在pathCopy里面只剩下一对孤立节点
							
		

//		// 现在根据severPaths里面的值来设置流量
		setDischarge(pathsCopy, networkNodes,consumeNodes ,severID);
		// 查找与服务器直接相连的点，之间的链路，是否超载严重（即需要的大于该点最大可能输入）step3
		// 找到路径

		for (int i : severGroup) {
			NetworkNode severNode = networkNodes[i];
			List<Link> links = severNode.getLinks();
			for (Link link : links) {
				int extraNeed = link.getExtraDischarge();// 差额为多少

				NetworkNode candiateSever = networkNodes[link.getToId()];
				List<Link> candiatelinks = candiateSever.getLinks();
				int maxDischarge = 0;// 与服务器相连的点的最大输入流量
				for (Link candiatelink : candiatelinks) {
					maxDischarge += candiatelink.getDischargeSum();
				}
				if ( Math.abs(extraNeed)>2*link.getDischargeSum()||maxDischarge< link.getCurrentDischarge()) {
					candiateSever.setLocatedServer(true);// 如果不能满足的话 那么只能为服务器了					
					severID.add(severID.size(),candiateSever.getId());//加入服务器
					
				}

			}
		}
*/
//		
		/************************************** 流量判断是否增加服务器********************************** */		
											
		return severID;


	}
	
	
	

	
									
	






	/**
	 * 获取消费点到最近的消费点
	 * 
	 * @param shortPath
	 * @return
	 */
	private List<Integer> findMinPath(List<List<Integer>> shortPath) {
		List<Integer> path = new ArrayList<>();
		int cost = 1000000;
		for (List<Integer> shortestPath : shortPath) {
			if (shortestPath.get(shortestPath.size() - 1) < cost && shortestPath.get(shortestPath.size() - 1) != 0) {
				cost = shortestPath.get(shortestPath.size() - 1);
				path = shortestPath;
			}
		}
		return path;
	}

	/**
	 * 找出出现次数最多的,排除id
	 * 
	 * @param paths
	 * @param id
	 * @return
	 */
	private int findMaxNode(List<List<Integer>> paths) {
		List<Integer> node = new ArrayList<>();// 存储出现的点号
		for (List<Integer> path : paths) {
			for (int i = 0; i < path.size(); i++) {
				if ((i==path.size()-2||i==0)) {// 最后一位是距离去除，找到最多的消费点
					node.add(path.get(i));
				}
			}
		}
		return findMaxAppear(node);

	}
	
	
	/**找到最多的重合点
	 * @param severPath
	 * @return
	 */
	private int findMaxSever(List<List<Integer>> severPath) {
		// TODO Auto-generated method stub
		List<Integer> node = new ArrayList<>();// 存储出现的点号
		for (List<Integer> path : severPath) {
			for (int i = 0; i < path.size(); i++) {
				if (i != (path.size() - 1)) {// 最后一位是距离去除，找到最多的重合点
					node.add(path.get(i));
				}
			}
		}
		return findMaxAppear(node);
		
	}

	/**
	 * 找出里面出现次数最多的
	 * 
	 * @param node
	 * @return
	 */
	private int findMaxAppear(List<Integer> array) {
		// map的key存放数组中存在的数字，value存放该数字在数组中出现的次数
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		for (int i = 0; i < array.size(); i++) {
			if (map.containsKey(array.get(i))) {
				int temp = map.get(array.get(i));

				map.put(array.get(i), temp + 1);
			} else {
				map.put(array.get(i), 1);
			}
		}

		Collection<Integer> count = map.values();

		// 找出map的value中最大的数字，也就是数组中数字出现最多的次数
		int maxCount = Collections.max(count);

		int maxNumber = 0;

		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			// 得到value为maxCount的key，也就是数组中出现次数最多的数字
			if (maxCount == entry.getValue()) {
				maxNumber = entry.getKey();
			}
		}

		return maxNumber;
	}

	/**
	 * id是服务器节点，到id的流量设为满足要求的
	 * 
	 * @param paths
	 * @param nodes
	 * @param id
	 * @param matrix
	 */
	/**
	 * id是服务器节点，到id的流量设为满足要求的
	 * 
	 * @param paths
	 * @param nodes
	 * @param id
	 * @param matrix
	 */
	public void setDischarge(List<List<Integer>> severPaths, NetworkNode[] nodes, ConsumeNode[] consumeNodes,
			List<Integer> severGroup) {
		for (List<Integer> list : severPaths) {// 该服务器连接的点
			list.remove(list.size() - 1);// 最后一个是最短距离
			// 注意这儿将需要的流量加进来了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！1！！！！！！！
			int discharge = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
			list.add(discharge);
			for (int j = 0; j < list.size() - 2; j++) {
				int require = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
				nodes[list.get(j + 1)].setDischargeTo(nodes[list.get(j)].getId(), require);// 设置流量
				// list.add(require);
			}
		}
	}
	
	
	/**
	 * id是服务器节点，到id的流量设为满足要求的
	 * 
	 * @param paths
	 * @param nodes
	 * @param id
	 * @param matrix
	 */
//	private void setDischarge1( List<List<Integer>> severPaths, NetworkNode[] nodes, int[] severGroup,
//			ConsumeNode[] consumeNodes) {
//			for (List<Integer> list : severPaths) {// 该服务器连接的点
//				list.remove(list.size() - 1);// 最后一个是最短距离
//				int start = list.get(0);//起始点
//				Boolean issever=false;
//				for (int severid : severGroup) {
//					if (start==severid) {
//						issever=true;
//					}
//				}
//				if (!issever) {
//					for (int j = 0; j < list.size() - 1; j++) {
//						int require = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
//						nodes[list.get(j + 1)].setDischargeTo(nodes[list.get(j)].getId(), require);						
//					}
//				}
//
//			}
//
//
//	}

	/**
	 * 找到id在list中的位置
	 * 
	 * @param list
	 * @param id
	 * @return
	 */
//	private int findLoacaltion(List<Integer> list, int id) {
//		int localtion = 0;
//		for (int i = 0; i < list.size(); i++) {
//			if (list.get(i) == id) {
//				localtion = i;
//			}
//		}
//
//		return localtion;
//	}

	/**
	 * 直到所有点的重复率只有2时停止，即只剩下两两互联的孤立点对或者孤立点
	 * 
	 * @param copyPaths
	 * @return
	 */
	private Boolean twoLeft(List<List<Integer>> copyPaths) {
		boolean is = false;
		List<Integer> node = new ArrayList<>();// 存储出现的点号
		for (List<Integer> path : copyPaths) {
			for (int i = 0; i < path.size(); i++) {
				if (i != (path.size() - 1)) {// 最后一位是距离，去除
					node.add(path.get(i));
				}
			}
		}
		// map的key存放数组中存在的数字，value存放该数字在数组中出现的次数
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		for (int i = 0; i < node.size(); i++) {
			if (map.containsKey(node.get(i))) {
				int temp = map.get(node.get(i));

				map.put(node.get(i), temp + 1);
			} else {
				map.put(node.get(i), 1);
			}
		}
		// 存储里面的个数
		Collection<Integer> count = map.values();

		for (Integer number : count) {
			if (number == 2) {
				is = true;
			} else {
				is = false;
			}
		}

		return is;
	}

}
